|
我们在该专栏中记录了我俩的刷题记录。我们更新的所有题目都在目录中。今天的题目是5. 最长回文子串 题目给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。思路：动态规划--区间型
特点： 给定一个序列/字符串，进行一些操作，最后一步会将序列/字符串去头/尾，剩下的会是一个区间[i,j]
状态自然定义为 f[i][j],表示面对子序列[i, ..., j]时的最优性质.
区间型动态规划的标志是要求区间内满足一定条件的最大长度等等，要通过由内往外扩散去做，
通常是按照区间的长度从小往大去遍历，比如区间长度为1，扩散到区间长度为2，...，一直往外扩
规律：
区间型 的数组都是2维的
要按照长度 j-i 从小到大的顺序计算- 状态：f[i][j] 表示从 i 到 j 的回文串长度
- 转移：
-- 1、i==j：dp[i][j]=True
-- 2、只有两个字母，s[i]==s[j]：dp[i][j]=True
-- 3、首尾相等，并且去掉首尾的内部也是回文串：s[i]==s[j] and dp[i+1][j-1]==True : dp[i][j] = True代码class Solution:
def longestPalindrome(self, s: str) -> str:
N = len(s)
dp = [[False]*N for _ in range(N)]
res = ''
if not s: return ''
if N == 1: return s
for k in range(N):
i, j = 0, k
while j < N:
# 条件1
if i == j:
dp[i][j] = True
# 条件2
elif j-i==1 and s[i] == s[j]:
dp[i][j] = True
# 条件3，首位相同，并且去掉首位内部也是回文串
elif s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if dp[i][j] and len(res) < (j-i+1):
res = s[i:j+1]
i += 1
j += 1
return res
|